package com.wfm.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * 滑动窗口，窗口大小为p.length()，统计这个窗口的字母个数，然后移动窗口，移动窗口的时候，把窗口的右下标对应字母数+1，把窗口的左下标对应字母数-1，
 * s="cbaebabacd" p="abc"
 * 用两个数组[26]分别统计s和p字母的个数，s肯定比p长才有必要统计，s先统计前三个也就是cba
 * 统计完后，先做一次判断，判断是否是字母异位词，只需要判断两个数组是否相等用Arrays.equals判断
 * 然后移动窗口，把e对应下标+1，c对应下标-1，再次判断数组。窗口移动sLen-pLen次就行，因为上一步窗口的右编辑已经在下标2也就是a那边了
 *
 * 时间o(pLen+(sLen-pLen)*26)个窗口，每个窗口判断是否相等都要比较26个字母统计数，所以时间复杂度o(sLen-pLen)*26,另外初始化的时候还要pLen次
 * 空间复杂度o(26)
 */
public class PFour38找到字符串中所有字母异位词 {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            int sLen = s.length(), pLen = p.length();

            if (sLen < pLen) {
                return new ArrayList<Integer>();
            }

            List<Integer> ans = new ArrayList<Integer>();
            int[] sCount = new int[26];
            int[] pCount = new int[26];
            for (int i = 0; i < pLen; ++i) {
                ++sCount[s.charAt(i) - 'a'];
                ++pCount[p.charAt(i) - 'a'];
            }

            if (Arrays.equals(sCount, pCount)) {
                ans.add(0);
            }

            for (int i = 0; i < sLen - pLen; ++i) {
                --sCount[s.charAt(i) - 'a'];
                ++sCount[s.charAt(i + pLen) - 'a'];

                if (Arrays.equals(sCount, pCount)) {
                    ans.add(i + 1);
                }
            }

            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    /**
     * 优化版 s="cbaebabacd" p="abc"
     * 1、初始遍历p和s，用[26]统计，p中出现的则对应下标字母-1，s出现则+1，[cba]ebabacd 所以刚开始初始化： count[0,0,0,...0]
     * 发现differ==0，则说明是字母异位词，把下标加到ans中也就是当前j的下标0，只要有！=0的，differ都要记录差异数
     *
     * 2、移动窗口，移动窗口的时候，把窗口的右下标对应字母数+1，把窗口的左下标对应字母数-1，
     * 然后需要更新differ，如果原来右下标对应字母数就是0，则differ+1，如果是-1，则differ-1，如果是1，则differ+1
     *                   如果原来左下标对应字母数就是0，则differ+1，如果是1，则differ-1，如果是-1，则differ+1
     * cbdeaebacd
     *                     a b c d e                           s   p
     * [cbd]eaebacd aab 【-2，0,1,1,0】 differ=3 处不一致，a不同：0！=2，c不同：1！=0，d不同：1！=0
     * c[bde]aebacd     【-2，0,0,1,1】 differ=3 处不一致，a不同：0！=1，c不同：1！=0，e不同：1！=0
     * cb[dea]ebacd     【-1，-1,0,1,1】differ=4
     * cbd[eae]bacd     【-1，-1,0,0,2】differ=3
     *                               -1->0 1->0 differ会减少
     *                               0->-1 0->1 differ会增加
     *                               其他情况-2->-3,1->2  differ不变
     *
     */
    public List<Integer> findAnagrams2(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] count = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++count[s.charAt(i) - 'a'];
            --count[p.charAt(i) - 'a'];
        }

        int differ = 0;
        for (int j = 0; j < 26; ++j) {
            if (count[j] != 0) {
                ++differ;
            }
        }

        if (differ == 0) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            if (count[s.charAt(i) - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i) - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            --count[s.charAt(i) - 'a'];

            if (count[s.charAt(i + pLen) - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i + pLen) - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            ++count[s.charAt(i + pLen) - 'a'];

            if (differ == 0) {
                ans.add(i + 1);
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Solution solution = new PFour38找到字符串中所有字母异位词().new Solution();
        List<Integer> anagrams = solution.findAnagrams("cbaebabacd", "abc");
        System.out.println(anagrams);
    }
}